package _17_graph;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: mornd
 * @dateTime: 2023/6/24 - 23:30
 * 迪克斯特拉 单源最短路径算法
 * 该算法以一个起始节点作为输入，并计算从起始节点到图中所有其他节点的最短路径。
 * 图片参考 img/构建图.png
 */
public class Dijkstra {

    @Test
    public void test() {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");

        v1.edges = List.of(new Edge(v3, 9), new Edge(v2, 7), new Edge(v6, 14));
        v3.edges = List.of(new Edge(v4, 11), new Edge(v6, 2));
        v2.edges = List.of(new Edge(v4, 15));
        v6.edges = List.of(new Edge(v5, 9));
        v4.edges = List.of(new Edge(v5, 6));
        v5.edges = List.of();

        List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6);

        dijkstra(v1, graph);

        for (Vertex vertex : graph) {
            System.out.println("name=" + vertex.name + ",dist=" + vertex.dist + ",from=" + (vertex.prev != null ? vertex.prev.name : null));
        }
    }

    /**
     * 1、将所有顶点标记为未访问，创建一个未访问的集合（如果顶点访问过了，则在集合中删除该顶点）
     * 2、为每个顶点赋值一个临时距离值，初始顶点为0，其它的为无穷大
     * 3、每次选择最小临时距离的未访问顶点，做为新的当前顶点
     * 4、对于当前顶点，遍历其所有未访问的邻居，并更新它们的临时距离为最小
     * 5、当前顶点的邻居处理完成后，把它从未访问集合中删除
     * @param v1 源
     * @param graph 顶点集合
     */
    private void dijkstra(Vertex v1, List<Vertex> graph) {
        List<Vertex> list = new ArrayList<>(graph);
        v1.dist = 0;

        while (!list.isEmpty()) {
            Vertex curr = chooseMinDistVertex(list);
            updateNeighborsDist(curr, list);
            list.remove(curr);
        }
    }

    /**
     * 更新邻居们的距离为最小
     * @param curr
     * @param list
     */
    private void updateNeighborsDist(Vertex curr, List<Vertex> list) {
        for (Edge edge : curr.edges) {
            Vertex neighbor = edge.linked;
            // contains=false，表示该顶点已经访问过了，并且它的dist已更新为最短的了，无需再调整了
            if(list.contains(neighbor)) {
                int newDist = curr.dist + edge.weight;
                if(newDist < neighbor.dist) {
                    neighbor.dist = newDist;
                    neighbor.prev = curr;
                }
            }
        }
    }

    /**
     * 从集合中查找距离最小的顶点返回
     * @param list
     * @return
     */
    private Vertex chooseMinDistVertex(List<Vertex> list) {
        Vertex min = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            if(list.get(i).dist < min.dist) {
                min = list.get(i);
            }
        }
        return min;
    }
}
